package com.zfl;

import java.util.LinkedList;

public class MaxSlidingWindow {

    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int index=0;
        for (int i = 0; i < nums.length; i++) {
            while(!queue.isEmpty()&&queue.peekFirst()<i-k+1) {
                queue.pollFirst();
            }

            while(!queue.isEmpty()&&nums[i]>nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);

            if (i>=k-1) {
                res[index] = nums[queue.peekFirst()];
                index++;
            }
        }
        return res;
    }
}
